洛谷 P2050 [NOI2012]美食节 题解

发表于 | 分类于 | | 热度: ℃

Description

有 $n$ 道菜，$m$ 个厨师。第 $j$ 个厨师做第 $i$ 道菜的时间为 $t_{i,j}$。有 $p_i$ 个人点第 $i$ 道菜。每个人的等待时间为 $0$ 到他点的菜品做完的时间。求最小的等待时间之和。

数据范围：$n<=40, m<=100, p<=800, t_{i,j}<=1000$ （其中 $p=∑p_i$）

Solution

把每道菜看做一个点，与源点连接，第 $i$ 道菜的流量为 $p_i$，费用为 $0$。把厨师拆成 $m$ * $p$ $(p=∑p_i)$ 个点，表示倒数第 $1–m$ 个时刻的所有厨师。把这些厨师与所有菜相连，流量为 $1$，费用为 $k$ * $a_{i,j}$。

证明：对于一道菜 $i$，其 被等待 的时间为 $k*a_{i,j}$（$k$ 为当前层数，$j$ 为当前厨师）。所有菜品的被等待时间相加即为所求的总等待时间。

最后把所有时刻的厨师与汇点相连，流量为 $1$，费用为 $0$。跑一遍费用流，即可得到 $60$ 分。

动态开点

先建立初始图，第一层的所有厨师与所有菜品和汇点相连。第一次一定找到了一条增广路，经过了其中一个厨师。第二次把当前厨师的下一层与所有菜品和汇点连上，再找一次增广路。到了最后所有的边都被连上了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int N = 400006, INF = 1 << 30;
struct edge
{
    int nxt, to, w, f;
} e[N * 2];
struct Pre
{
    int node, line;
} pre[N * 2];
int n, m, s, t, w = 1, sum = 0, cnt = 1, cost = 0;
int head[N], dis[N], vis[N], p[N], a[106][106], cook[N], dish[N];

inline int read()
{
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    return x * f;
}

int ID(int a, int b) { return (a - 1) * sum + b + n; }

void add(int x, int y, int w, int f)
{
    e[++cnt] = (edge) { head[x], y, w, f };
    head[x] = cnt;
    e[++cnt] = (edge) { head[y], x, 0, -f };
    head[y] = cnt;
}

bool spfa()
{
    for(int i = 0; i <= t; i++)
        vis[i] = 0, dis[i] = 0x3f3f3f3f, pre[i].node = pre[i].line = -1;
    queue <int> q;
    q.push(s);
    dis[s] = 0;
    while(!q.empty())
    {
        int a = q.front();
        q.pop();
        vis[a] = 0;
        for(int i = head[a]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if(dis[v] > dis[a] + e[i].f && e[i].w)
            {
                dis[v] = dis[a] + e[i].f;
                pre[v].node = a;
                pre[v].line = i;
                if(!vis[v]) { vis[v] = 1; q.push(v); }
            }
        }
    }
    return dis[t] == 0x3f3f3f3f ? false : true;
}

void EK()
{
    while(spfa())
    {
        int minn = INF;
        for(int i = t; i != s; i = pre[i].node)
            minn = min(minn, e[pre[i].line].w);
        for(int i = t; i != s; i = pre[i].node)
        {
            e[pre[i].line].w -= minn;
            e[pre[i].line ^ 1].w += minn;
        }
        cost += minn * dis[t];
        int u = pre[t].node;
        add(u + 1, t, 1, 0);
        for(int i = 1; i <= n; i++)
            add(i, u + 1, 1, a[i][cook[u + 1]] * (dish[u + 1]));
    }
}

int main()
{
    n = read(); m = read();
    for(int i = 1; i <= n; i++) p[i] = read(), sum += p[i];
    s = 0, t = sum * m + n + 1;
    for(int i = 1; i <= n; i++)
    {
        add(s, i, p[i], 0);
        for(int j = 1; j <= m; j++) a[i][j] = read();
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= sum; j++)
        {
            int tmp = ID(i, j);
            cook[tmp] = i, dish[tmp] = j;
        }
    }
    for(int i = 1; i <= m; i++)
    {
        for(int j = 1; j <= n; j++)
            add(j, ID(i, 1), 1, a[j][i]);
        add(ID(i, 1), t, 1, 0);
    }
    EK();
    printf("%d", cost);
    return 0;
}